package com.itzmn.newcode.offer;

import java.util.ArrayList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/18 10:22
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 剑指Offer 得到二叉搜索树中第k小的节点
 *
 *  思路：
 *   中序遍历树，得到集合，该位置就是第几小的值
 */

public class GetBinTreeMinNum {

    public static void main(String[] args) {

    }

    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if (k==0){
            return null;
        }

        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        zhongxu(treeNodes,pRoot);
        if (k>treeNodes.size()){
            return null;
        }
        return treeNodes.get(k-1);
    }
    public void zhongxu(ArrayList<TreeNode> treeNodes,TreeNode root){

        if (root == null){
            return;
        }
        if (root.left!=null){
            zhongxu(treeNodes,root.left);
        }
        treeNodes.add(root);
        if (root.right!=null){
            zhongxu(treeNodes,root.right);
        }
    }
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

}
